package com.leetcode.recursion;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Permute {
	public static void permute(String s) {
		char[] cs = s.toCharArray();
		permute(cs, 0, cs.length-1);

	}

	public static void permute(char[] cs, int level, int len) {
		int i = 0;
		if (level == len) {
			System.out.println(new String(cs));
		} else {
			for (i = level; i <= len; i++) {
				if (i == level) {
					permute(cs, level + 1, len);
				}else{
					char temp = cs[level];
					cs[level] = cs[i];
					cs[i] = temp;
					
					permute(cs, level + 1, len);
					
					cs[i]=cs[level];
					cs[level] = temp;
				}
				
			}
		}
	}

	public static void circulate(String s) {
		Stack<String[]> stack = new Stack<>();
		List<String> results = new ArrayList<>();
		stack.push(new String[]{s,""});
		
		do{
			String[] popStrs = stack.pop();
			String oldStr = popStrs[1];
			String stackStr = popStrs[0];
			for(int i=0;i<stackStr.length();i++){
				String[] strs = new String[]{stackStr.substring(0, i)+stackStr.substring(i+1),oldStr+stackStr.substring(i,i+1)};
				if(strs[0].length()==0){
					results.add(strs[1]);
				}else{
					stack.push(strs);
				}
			}
		}while(!stack.isEmpty());
		System.out.println(results);
		
	}

	public static void myPermute1(String s) {
		myPermute1(new StringBuilder(s), s.length(), new StringBuilder());
	}

	public static void myPermute1(StringBuilder sb, int len, StringBuilder fixSb) {
		if (len == 1) {
			// System.out.println(fixSb.append(sb).toString());
		} else {
			for (int i = 0; i < len; i++) {
				StringBuilder sb1 = new StringBuilder(sb);
				char temp = sb1.charAt(i);
				sb1.deleteCharAt(i);

				StringBuilder fixSb1 = new StringBuilder(fixSb);
				fixSb1.append(temp);
				myPermute1(sb1, len - 1, fixSb1);
			}

		}

	}

	public static void main(String[] args) {
		String s = "abc";
		circulate(s);
//		long begin1 = System.currentTimeMillis();
//		permute(s);
//		long end1 = System.currentTimeMillis();
//		System.out.println(end1 - begin1);

		// long begin2 = System.currentTimeMillis();
		// myPermute1(s);
		// long end2 = System.currentTimeMillis();
		// System.out.println(end2-begin2);

		// permute(s);

	}
}
